Since the beginning of computer programming, bugs have been present in software. Given enough users of a program, bugs will be found, which reflect poorly on the software vendor. Thus, an important part of software development is testing to eliminate bugs in software, and to have the software designed to otherwise handle unusual circumstances. That is one reason why Beta testing is used, so that by sheer numbers, many users (who understand that bugs are likely early in the development process) can help to debug a product before it is sold to consumers. Other testing is performed in a black-box type environment, in which testers intentionally run software through numerous combinations and permutations, looking for bugs.
Some bugs and other computer-related problems are not necessarily a result of programming errors, but instead result from a combination of events that occur in a certain order. For example, one common test scenario that follows such an order-dependent pattern is the installation of software packages. In general, applications may require that a specific version of a runtime (e.g., managed execution) environment be present, and/or that runtime environments be installed in a certain order. Thus, in certain scenarios, testers need to test sequences of operations in which the order of those operations is important. Consider four versions of a runtime environment, such as versions A, B, C, and D in this example. An application may be compiled against any of these and may work only if a specific version of the runtime environment is installed. Further, installing such runtime environment one after another needs to provide a stable environment. Thus, A, B, C, D may be a valid installation order, but installing in the order A, C, B, D may cause instability.
A typical test requires that all possible permutations of the runtime environments be installed, and after each installation step, the attempts to run a set of one or more applications, (which were compiled with different versions of the runtime environment), verifying whether the applications work (or do not work) as expected. To exhaustively test four independent operations such as installations (represented by elements) A, B, C, D in which the order of installations matters, a tester needs to run through twenty-four permutations of the installations, as in the following table:
{A, B, C, D}{B, A, C, D}{C, A, B, D}{D, A, B, C}{A, B, D, C}{B, A, D, C}{C, A, D, B}{D, A, C, B}{A, C, B, D}{B, C, A, D}{C, B, A, D}{D, B, A, C}{A, C, D, B}{B, C, D, A}{C, B, D, A}{D, B, C, A}{A, D, B, C}{B, D, A, C}{C, D, A, B}{D, C, A, B}{A, D, C, B}{B, D, C, A}{C, D, B, A}{D, C, B, A}
Although this is not exceptionally difficult given the number of versions in the simple example above, adding one new element to the set of operations makes the test suite grow by a factor of five, that is, 120 tests. The size of the test suite for n elements is n factorial (n!), which quickly becomes unworkable in many situations with many elements, particularly when each element in a test case corresponds to a somewhat time-consuming operation, such as performing a software package installation. Simply selecting certain test cases and not others would likely leave important sequences of operations untested, providing an unreliable test.
What is needed is a way to provide a test suite that has a reduced number of test cases corresponding to sequences of computer-related operations. At the same time, any such reduction of test cases cannot cause important test sequences to be missed.